import LinedList, { Node } from "./实现单向链表LinkedList";

// 新增节点类型
export class DoblyNode<T> extends Node<T> {
  prev: DoblyNode<T> | null = null;
  next: DoblyNode<T> | null = null;
}
class DoblyLinkedList<T> extends LinedList<T> {
  head: DoblyNode<T> | null = null;
  tail: DoblyNode<T> | null = null;
  // 重写新增
  append(item: T): void {
    let newNode = new DoblyNode(item);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      newNode.prev = null;
    } else {
      newNode.prev = this.tail;
      newNode.next = null;
      this.tail!.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }
  // 向前插入
  prepend(item: T): void {
    if (!this.head) {
      this.append(item);
      return;
    }
    let newNode = new DoblyNode(item);
    newNode.next = this.head;
    this.head!.prev = newNode;
    this.head = newNode;
    this.size++;
  }

  // 倒序遍历
  postTraverse(): string {
    let current = this.tail;
    const values: T[] = [];
    while (current) {
      values.push(current.data);
      current = current.prev;
    }

    return values.join("->");
  }

  // 重新插入,很容易找到上一个节点
  insert(position: number, element: T): T | null {
    const newNode = new DoblyNode(element);
    if (position < 0 && position > this.size) {
      return null;
    } else if (position === 0) {
      this.prepend(element);
    } else if (position === this.size) {
      this.append(element);
    } else {
      let current = this.head;
      let index = 0;
      while (index < position) {
        current = current?.next ?? null;
        index++;
      }
      const preNode = current!.prev;
      preNode!.next = newNode;
      newNode.prev = preNode;
      newNode.next = current;
      current!.prev = newNode;
      this.size++;
    }

    return newNode.data;
  }

  // 删除节点，比较麻烦,智取
  removeAt(position: number): T | undefined {
    let current: DoblyNode<T> | null = null;
    if (position < 0 && position >= this.size) {
      return undefined;
    } else if (this.size === 0) {
      return undefined;
    } else if (position === 0 && this.size === 1) {
      if (this.size === 1) {
        current = this.head;
        this.head = null;
        this.tail = null;
      } else {
        current = this.head!.next!;
        current.prev = null;
        this.head = current;
      }
    } else if (position === this.size - 1) {
      current = this.tail!;
      this.tail = this.tail!.prev!;
      this.tail.next = null;
    } else {
      current = super.getNode(position) as DoblyNode<T>;
      const preNode = current.prev;
      const nextNode = current!.next;
      preNode!.next = nextNode;
      nextNode!.prev = preNode;
    }
    this.size--;

    return current!.data;
  }
}

const doblyLinkedList1 = new DoblyLinkedList();

doblyLinkedList1.append("a");
doblyLinkedList1.append("b");
doblyLinkedList1.append("c");
doblyLinkedList1.append("d");
doblyLinkedList1.append("f");
doblyLinkedList1.prepend("a1");
console.log(doblyLinkedList1.traverse());
console.log(doblyLinkedList1.postTraverse());

// doblyLinkedList1.insert(0, "0a");
doblyLinkedList1.insert(2, "0aa");
// doblyLinkedList1.insert(7, "f1");
console.log(doblyLinkedList1.traverse());
console.log(doblyLinkedList1.postTraverse());

doblyLinkedList1.removeAt(2);
doblyLinkedList1.removeAt(2);
console.log(doblyLinkedList1.traverse());
console.log(doblyLinkedList1.postTraverse());
